package suanfa;

import java.util.*;

public class cutOffTree {
    int m,n;
    public int cutOffTree(List<List<Integer>> f) {
        m=f.size();
        n=f.get(0).size();
        List<int[]> trees=new ArrayList<>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(f.get(i).get(j)>1) trees.add(new int[]{i,j});
            }
        }
        Collections.sort(trees,(a, b)->{
            return f.get(a[0]).get(a[1])-f.get(b[0]).get(b[1]);
        });
        //2.按照顺序进行砍树
        int ret=0;
        int bx=0,by=0;
        for(int[] tree:trees){
            int x=tree[0],y=tree[1];
            int step=bfs(f,bx,by,x,y);
            if(step==-1) return -1;
            ret+=step;
            bx=x;by=y;
        }
        return ret;
    }
    public int bfs(List<List<Integer>> f,int bx,int by,int ex,int ey){
        int[] dx={0,0,1,-1};
        int dy[]={1,-1,0,0};
        if(bx==ex && by==ey) return 0;
        Queue<int[]> q=new LinkedList<>();
        boolean[][] vis=new boolean[m][n];
        q.add(new int[]{bx,by});
        vis[bx][by]=true;
        int step=0;
        while(!q.isEmpty()){
            step++;
            int sz=q.size();
            while(sz--!=0){
                int[] t=q.poll();
                int a=t[0],b=t[1];
                for(int i=0;i<4;i++){
                    int x=a+dx[i],y=b+dy[i];
                    if(x>=0 && x<m && y>=0 && y<n &&!vis[x][y] && f.get(x).get(y)!=0){
                        if(x==ex && y==ey) return step;
                        q.add(new int[]{x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
}
